from typing import List


class Solution:
    """
    方法：回溯算法
    Args:
        n: 整数，表示括号对的数量
    Returns:
        List[str]: 所有有效的括号组合
    Time: O(4^n/√n)，卡特兰数的增长速度
    Space: O(n)，递归调用栈的深度
    """
    def generateParenthesis(self, n: int) -> List[str]:
        m = n * 2
        ans = []
        path = [''] * m # 所有括号长度都是一样的 m

        # 目前填了 i 个括号
        # 这 i 个括号中有 open 个左括号，i-open 个右括号
        def backtrack(i: int, open: int) -> None:
            if i == m: # 括号构造完毕
                ans.append(''.join(path))
                return
            if open < n: # 可以填左括号
                path[i] = '('
                backtrack(i+1, open + 1) # 多了一个左括号
            if i - open < open: # 可以填右括号
                path[i] = ')'
                backtrack(i+1, open)
        backtrack(0, 0)
        return ans
    

    """
    方法：回溯算法，通过记录左括号位置生成有效括号组合
    Args:
        n: 整数，表示括号对的数量
    Returns:
        List[str]: 所有有效的括号组合
    Time: O(4^n/√n)，卡特兰数的增长速度
    Space: O(n)，递归调用栈的深度
    """

    def generateParenthesis1(self, n: int) -> List[str]:
        ans = []
        path = [] # 记录左括号的下标

        # 目前填了 i 个括号
        # 这 i 个括号中的左括号个数 - 右括号个数 = balance
        def backtrack(i: int, balance: int) -> None:
            if len(path) == n:
                s = [')'] * (n * 2)
                for j in path:
                    s[j] = '('
                ans.append(''.join(s))
                return
            # 枚举填 close=0,1,2,...,balance 个右括号
            for close in range(balance + 1):
                # 先填 close 个右括号，然后填 1 个左括号，记录左括号的下标 i+close
                path.append(i + close)
                backtrack(i + close + 1, balance - close + 1)
                path.pop()
        backtrack(0, 0)
        return ans